Gra w zielone

Limit pamięci: 32 MB

Gra w zielone jest grą dla dwóch graczy - nazwijmy ich Ania i Bolek - polegającą na przesuwania pionka po planszy.

Część pól planszy jest pokolorowana na zielono, a pozostałe są białe. Wszystkie pola są ponumerowane liczbami naturalnymi z zakresu , pola o numerach z zakresu należą do Ani, natomiast pola o numerach należą do Bolka.

Dla każdego pola dany jest zbiór następników, zawierający te pola planszy, do których można z niego przejść w jednym ruchu. Zbiory te zostały tak dobrane, że z pola należącego do Ani można przejść w jednym ruchu tylko na pole należące do Bolka i odwrotnie.

Na początku gry ustawiamy pionek na dowolnym polu, a następnie gracze na przemian przestawiają pionek ze swojego pola na dowolny następnik tego pola - należący do przeciwnika. Grę rozpoczyna właściciel pola, z którego zaczynamy rozgrywkę. Zakładamy, że wszystkie pola mają niepuste zbiory następników, a więc zawsze można wykonać ruch. Gra kończy się w momencie, gdy pionek stanie po raz drugi na tym samym polu. Jeśli w sekwencji ruchów, od pierwszego do powtórnego zajęcia tego pola, pionek stanął przynajmniej raz na polu zielonym, to wygrywa Ania, w przeciwnym przypadku wygrywa Bolek.

Powiemy, że Ania ma strategię wygrywającą dla danego pola początkowego, jeśli istnieje metoda gwarantująca jej wygraną w rozgrywce zaczynającej się od tego pola, niezależnie od tego, jakie ruchy będzie wykonywał Bolek.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis planszy do gry w zielone,
• znajdzie zbiór pól planszy, dla których Ania ma strategię wygrywającą,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisane są dwie nieujemne liczby całkowite , oddzielone pojedynczym odstępem, oznaczające odpowiednio: liczbę pól należących do Ani i liczbę pól należących do Bolka. Liczby , spełniają warunek: . W kolejnych a+b wierszach opisano pola planszy - najpierw pola należące do Ani, a następnie pola należące do Bolka. Wiersz o numerze , dla , zawiera na początku liczby całkowite , oddzielone pojedynczym odstępem, oznaczające odpowiednio kolor pola o numerze ( oznacza kolor biały, - kolor zielony), oraz liczbę następników tego pola. Następnie w tym wierszu zapisane jest liczb całkowitych (), pooddzielanych pojedynczymi odstępami, będącymi numerami następników danego pola. Liczba pól zielonych na planszy nie przekracza . Suma liczb następników wszystkich pól na planszy nie przekracza .

Wyjście

Pierwszy wiersz standardowego wyjścia powinien zawierać dokładnie jedną liczbę całkowitą , oznaczającą liczbę pól, na których Ania ma strategię wygrywającą. Następne wierszy powinno zawierać numery tych pól zapisane w kolejności rosnącej - każda liczba powinna zostać zapisana w osobnym wierszu.

Przykład

Dla danych wejściowych:

5 3
0 2 6 7
0 3 6 7 8
0 1 8
1 1 7
1 1 8
1 2 1 2
0 2 1 2
0 2 3 4

poprawną odpowiedzią jest:

5
1
2
4
6
7

Autor zadania: Marcin Jurdziński.